//
// Created by DengLibin on 2018/12/16 0016.
//
#include <iostream>
using namespace std;
/*霍夫曼树节点*/
class HuoFuManTreeNode
{
private:
    unsigned int  weight; //权重
    HuoFuManTreeNode * leftNode, *rightNode; //左右节点
public:
    void setWeight(unsigned int weight)
    {
        this->weight = weight;
    }
    unsigned int getWeight()
    {
        return this->weight;
    }
    void setLeftNode(HuoFuManTreeNode * huoFuManTreeNode)
    {
        this->leftNode = huoFuManTreeNode;
    }

    HuoFuManTreeNode * getLeftNode()
    {
        return this->leftNode;
    }

    void setRightNode(HuoFuManTreeNode * huoFuManTreeNode)
    {
        this->rightNode = huoFuManTreeNode;
    }

    HuoFuManTreeNode * getRigthNode()
    {
        return this->rightNode;
    }
};
/*队列节点*/
class QueueNode
{
private:
    HuoFuManTreeNode * treeNode; //霍夫曼树节点
    char data;//字符
    unsigned int weight; //权值（和霍夫曼树节点一样）
    QueueNode * nextNode;//下一个节点
public:
    void setTreeNode(HuoFuManTreeNode * treeNode)
    {
        this->treeNode = treeNode;
    }
    HuoFuManTreeNode * getTreeNode()
    {
        return this->treeNode;
    }
    void setWiegth(unsigned int weight)
    {
        this->weight = weight;
    }

    unsigned int getWeight()
    {
        return this->weight;
    }
    void setNextNode(QueueNode * nextNode)
    {
        this->nextNode = nextNode;
    }

    QueueNode * getNextNode()
    {
        return this->nextNode;
    }

    void setData(char data)
    {
        this->data = data;
    }
    char getData()
    {
        return this->data;
    }

};
/*有序队列,从小到大排序,用链表实现*/
class Queue
{
private:
    unsigned int size = 0; //大小
    QueueNode * firstNode;//头节点
public:

    int getSize()
    {
        return this->size;
    }
    QueueNode * getFirstNode()
    {
        return this->firstNode;
    }
    //添加元素
    void addNode(QueueNode * queueNode)
    {
        queueNode->setNextNode(nullptr); //先把插入的节点的下一个节点设为null
        if (size == 0)
        {
            firstNode = queueNode;
            size++;
            return;
        }
        else
        {
            QueueNode * preNode = firstNode;
            if (queueNode->getWeight() < preNode->getWeight()) //比第一个节点还小
            {
                firstNode = queueNode;
                firstNode->setNextNode(preNode);
                size++;
                return; //插入完成，结束
            }
            else //比第一个节点大
            {

                //队列至少2个就节点
                while (preNode->getNextNode() != nullptr)
                {
                    //比下一个节点小
                    if (queueNode->getWeight() <= preNode->getNextNode()->getWeight())
                    {
                        QueueNode * tempNode = preNode->getNextNode(); //原来的下一个节点
                        preNode->setNextNode(queueNode); //插入的节点成为下一个节点
                        queueNode->setNextNode(tempNode); //原来的下一个节点成为插入的节点的下一个节点
                        size++;
                        return; //插入完成，结束
                    }
                    preNode = preNode->getNextNode();
                }
                //到这一步可知插入的节点比队列中的所有节点都大
                if (preNode->getNextNode() == nullptr)
                {
                    preNode->setNextNode(queueNode);
                    size++;
                    return; //插入完成，结束
                }
            }

        }

    }

    void showQueueData()
    {
        cout << "队列大小:" <<size<< endl;
        QueueNode *tempNode = this->getFirstNode();
        while (tempNode != nullptr)
        {
            cout << tempNode->getData() <<"--->"<< tempNode->getWeight()<<endl;
            tempNode = tempNode->getNextNode();
        }
    }
    //取元素(只取HuoFuManTreeNode的节点即可)
    HuoFuManTreeNode * take()
    {
        HuoFuManTreeNode * returnNode = nullptr;
        if (this->size > 0)
        {
            QueueNode * tempNode = this->firstNode;
            returnNode = tempNode->getTreeNode();
            this->firstNode = tempNode->getNextNode();
            this->size--;
            delete tempNode;
        }
        return returnNode;
    }

    //转成霍夫曼树
    HuoFuManTreeNode * toHuoFuManTree()
    {
        while (size != 1) //最后队列中只有一个根节点
        {
            int weight_1 = getFirstNode()->getWeight(); //权重
            int newWeight = weight_1 + getFirstNode()->getNextNode()->getWeight();
            //取出较小的两个节点
            HuoFuManTreeNode * leftNode = take();
            HuoFuManTreeNode * rightNode = take();
            //新生成一个新的树节点
            HuoFuManTreeNode * treeNode = new HuoFuManTreeNode();
            //设置左节点
            treeNode->setLeftNode(leftNode);
            //设置右节点
            treeNode->setRightNode(rightNode);
            //设置权重
            treeNode->setWeight(newWeight);
            //新的节点再添加队列
            QueueNode * queueNode  = new QueueNode();
            queueNode->setWiegth(treeNode->getWeight());
            queueNode->setNextNode(nullptr);
            queueNode->setTreeNode(treeNode);
            this->addNode(queueNode);
        }
        return this->take(); //取出最后一个节点就是树的根节点
    }
};

//展示树结构
void showTree(HuoFuManTreeNode * treeNode,int deep)
{
    if (treeNode != nullptr) {
        for (int i = 0; i < deep; i++)
        {
            cout << "-";
        }
        cout << treeNode->getWeight() << endl;
        showTree(treeNode->getLeftNode(), deep+1);
        showTree(treeNode->getRigthNode(), deep+1);
    }

}

/*根据传入的字符串获取一颗霍夫曼树。返回根节点*/
HuoFuManTreeNode * getHuoFuManTree(const char * str)
{
    //求每个字符的权重（出现的次数,下标是字符的ascii码,值是权重）
    int * buf = new int[256]{0};//一个字符占一个字节，一个字节8位，最大能表示256个字符

    for(int i = 0; str[i] !='\0'; i++)
    {
        int index = (unsigned int)str[i];//字符的ascii 码
        buf[index]++;
        //cout << (char)index<<"--->"<<buf[index]<<endl;
    }


    //添加到队列中
    Queue *queue = new Queue();
    for (int i = 0; i < 256; i++)
    {
        if (buf[i] != 0)
        {
            QueueNode * queueNode = new QueueNode();
            queueNode->setNextNode(nullptr);
            queueNode->setWiegth(buf[i]); //权重
            HuoFuManTreeNode * treeNode = new HuoFuManTreeNode();
            treeNode->setWeight(buf[i]);
            queueNode->setTreeNode(treeNode);
            queueNode->setData((char)i);
            queue->addNode(queueNode);
        }
    }
    delete[] buf;
    queue->showQueueData();
    //生成霍夫曼树
    HuoFuManTreeNode * root = queue->toHuoFuManTree();
    cout << "霍夫曼树：" << endl;
    showTree(root,0);


    //delete queue;
    return root;

}


int main40(int argc, char * argv[])
{
    const char * str= "abbbccccdddddddeeeeeeeefffffffff";
    getHuoFuManTree(str);
    return 0;
}

